A line drawing algorithm is a graphical algorithm for approximating a line segment on discrete graphical media. On discrete media, such as pixel-based displays and printers, line drawing requires such an approximation (in nontrivial cases).
On continuous media, by contrast, no algorithm is necessary to draw a line. For example, oscilloscopes use natural phenomena to draw lines and curves.
dx = x2 - x1
dy = y2 - y1
for x from x1 to x2 {
y = y1 + (dy) * (x - x1)/(dx)
plot(x, y)
}
It is assumed here that the points have already been ordered so that . This algorithm works just fine when (i.e., slope is less than or equal to 1), but if (i.e., slope greater than 1), the line becomes quite sparse with lots of gaps, and in the limiting case of , only a single point is plotted.
The naïve line drawing algorithm is inefficient and thus, slow on a digital computer. Its inefficiency stems from the number of operations and the use of floating-point calculations. Line drawing algorithms such as Bresenham's or Wu's are preferred instead.
The following is a partial list of line drawing algorithms:
Fundamentals of Computer Graphics, 2nd Edition, A.K. Peters by Peter Shirley